問題解決力を鍛えるアルゴリズムとデータ構造演習問題
2026-05-13
6.1
この問題は「座標圧縮」と呼ばれる典型的な処理です。
各要素が全体で何番目に小さいか（0始まりの順位）を求める問題で、ソートを使うと (O(N \log N)) で実現できます。
アイデア
値と元の位置をペアにする
配列aの各要素に、「値」と「もともとあったインデックス」をセットにしたタプルを作ります。
例：a = [12, 43, 7, 15, 9]→[(12,0), (43,1), (7,2), (15,3), (9,4)]値でソートする
タプルのリストを「値」の昇順に並べ替えます。
ソート後：[(7,2), (9,4), (12,0), (15,3), (43,1)]
こうすると、先頭から順に「0番目に小さい値、1番目に小さい値…」と…